package com.ljc;

import java.util.ArrayList;
import java.util.List;

/**
 * @author clj
 * @date 2022/12/6
 * @desc Given an integer numRows, return the first numRows of Pascal's triangle.
 * In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
 * <p>
 * Example 1:
 * Input: numRows = 5
 * Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 * <p>
 * Example 2:
 * Input: numRows = 1
 * Output: [[1]]
 * <p>
 * <p>
 * 杨辉三角形，又称帕斯卡三角形、贾宪三角形、海亚姆三角形、巴斯卡三角形，是二项式系数的一种写法，形似三角形，
 * 在中国首现于南宋杨辉的《详解九章算法》得名，其在书中说明是引自贾宪的《释锁算书》，故又名贾宪三角形。
 *
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1
1  10  45 120 210 252 210 120  45  10   1
------------------------
[
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
]

 * 杨辉三角形第 n 层（顶层称第 0 层，第 1 行，第 n 层即第 n+1 行，此处 n 为包含 0 在内的自然数）
 */
public class E118PascalTriangle {
    public static void main(String[] args) {
        int numRows = 10;
        System.out.println(generate(numRows));

        System.out.println("------------------------");

        showYangHuiTriangle(numRows);

    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }

    public static void showYangHuiTriangle(int numRows) {

        // allocate triangular array
        int[][] odds = new int[numRows + 1][];
        for (int n = 0; n <= numRows; n++) {
            odds[n] = new int[n + 1];

            // fill triangular array

            for (int k = 0; k < odds[n].length; k++) {
                /*
                 * compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
                 */
                int lotteryOdds = 1;
                for (int i = 1; i <= k; i++) {
                    lotteryOdds = lotteryOdds * (n - i + 1) / i;
                }

                odds[n][k] = lotteryOdds;
            }
        }
        // print triangular array
        for (int[] row : odds) {
            for (int odd : row) {
                System.out.printf("%4d", odd);
            }
            System.out.println();
        }
    }

}
